//1.从尾部到头打印链表
//思路1:pre、cur、next 三指针移动；
//思路2:递归反转
// comments：good

#include <iostream>
#include <vector>
#include <stack>

struct ListNode {
      int val;
      struct ListNode *next;
      ListNode(int x) :
            val(x), next(NULL) {
      }
};

class Solution1 {
public:
    ListNode* ReverseList(ListNode* pHead) {
           //反转链表
        if (pHead == nullptr) return nullptr;

        ListNode* cur = pHead;
        ListNode* pre = nullptr;
        ListNode* next = cur->next;

        while (cur != nullptr){
            next = cur->next;
            cur->next = pre;
            pre = cur;
            cur = next;
        };
        return pre;
    }
};


// 递归解题思路
// public ListNode reverseList(参数0) {
//     if (终止条件)
//         return;
 
//     逻辑处理（可能有，也可能没有，具体问题具体分析）
 
//     //递归调用
//     ListNode reverse = reverseList(参数1);
 
//     逻辑处理（可能有，也可能没有，具体问题具体分析）
// }

class Solution2 {
public:
    ListNode* ReverseList(ListNode* head) {
        //终止条件
        if (head == nullptr || head->next == nullptr)
            return head;
        //保存当前节点的下一个结点
        ListNode* next = head->next;
        //从当前节点的下一个结点开始递归调用
        ListNode* reverse = ReverseList(next);
        //reverse是反转之后的链表，因为函数reverseList
        // 表示的是对链表的反转，所以反转完之后next肯定
        // 是链表reverse的尾结点，然后我们再把当前节点
        //head挂到next节点的后面就完成了链表的反转。
        next->next = head;
        //这里head相当于变成了尾结点，尾结点都是为空的，
        //否则会构成环
        head->next = nullptr;
        return reverse;
    }
};